package com.c2b.algorithm.leetcode.base;

import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/">K 个一组翻转链表(Reverse Nodes in k-Group)</a>
 * <p>给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], k = 2
 *      输出：[2,1,4,3,5]
 *
 * 示例 2：
 *      输入：head = [1,2,3,4,5], k = 3
 *      输出：[3,2,1,4,5]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>链表中的节点数目为 n</li>
 * <li>1 <= k <= n <= 5000</li>
 * <li>0 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 * <br><b>进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？</b>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/5/5 9:20
 */
public class LC0025ReverseNodesInKGroup_H {

    static class Solution {
        public ListNode reverseKGroup2(ListNode head, int k) {
            ListNode dummyHead = new ListNode(-1, head);
            // currGroupHeadNode：用于记录当前组的前一个节点
            ListNode currGroupPrevNode = dummyHead;
            ListNode currGroupTailNode;
            while (currGroupPrevNode.next != null) {
                // currGroupTailNode:用于记录当前组的尾节点
                currGroupTailNode = currGroupPrevNode;
                // 从当前节点开始，向后找到 K 个节点，记为一组。如果当前组节点数不足 K 个，不需要反转
                for (int i = 0; i < k && currGroupTailNode != null; i++) {
                    currGroupTailNode = currGroupTailNode.next;
                }
                // ==> 特殊情况：当前组节点数量不足K个。结束循环
                if (currGroupTailNode == null) {
                    break;
                }
                // ==> 当前组节点数量达到k个的：
                // 1.断开链表。记录下一组的头节点，让当前组的尾节点指向null
                ListNode nextGroupHeadNode = currGroupTailNode.next;
                currGroupTailNode.next = null;
                // 记录当前组的头节点，反转后正好变成尾节点，与下一组的头节点拼接
                ListNode currGroupTailNodeAfterReserve = currGroupPrevNode.next;
                // 2.反转链表 并 进行连接
                currGroupPrevNode.next = reverse(currGroupPrevNode.next);
                currGroupTailNodeAfterReserve.next = nextGroupHeadNode;
                // 来到下一段 k
                currGroupPrevNode = currGroupTailNodeAfterReserve;
            }
            return dummyHead.next;
        }

        public ListNode reverseKGroup(ListNode head, int k) {
            if (k == 1) {
                return head;
            }
            // 统计链表中节点的数量，计算可以分成几组
            int nodeCount = 0;
            ListNode currNode = head;
            while (currNode != null) {
                ++nodeCount;
                currNode = currNode.next;
            }
            // 组数 = nodeCount/k，因为不满一组不需要反转
            ListNode dummyHead = new ListNode(-1);
            ListNode dummyCurr = dummyHead;
            for (int i = 0; i < nodeCount / k; i++) {
                currNode = head;
                for (int j = 0; j < k - 1; j++) {
                    currNode = currNode.next;
                }
                // nextList:下一组的头节点
                ListNode nextList = currNode.next;
                // 断开并反转
                currNode.next = null;
                dummyCurr.next = reverse(head);
                while (dummyCurr.next != null) {
                    dummyCurr = dummyCurr.next;
                }
                // 进入下一组
                head = nextList;
            }
            // 处理不足一组的剩余节点
            dummyCurr.next = head;
            return dummyHead.next;
        }

        /**
         * 反转链表
         */
        private ListNode reverse(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution solution = new Solution();
        Printer.printListNode(solution.reverseKGroup(head, 2));
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);
        Printer.printListNode(solution.reverseKGroup(head2, 3));
    }
}
